package com.javabasic.algorithm.sword_of_offer;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see [剑指 Offer II 029. 排序的循环链表 - 力扣（LeetCode）](https://leetcode.cn/problems/4ueAj6/)
 * 题目缺少条件，升序需要满足顺时针条件
 * @since Created by work on 2022/6/18 22:47
 */
public class 排序的循环链表 {

    public Node insert(Node head, int insertVal) {

        /**
         * 特殊处理：节点为空或者为一个元素的时候，直接追加要插入的元素
         */
        Node target = new Node(insertVal);
        if (head == null) {
            target.next = target;
            return target;
        }
        if (head.next == head) {
            head.next = new Node(insertVal, head);
            return head;
        }


        Node tempHead= head;
        boolean findPos = false;
        Node transNode = null;
        while (true) {
            if (tempHead.val <= insertVal && tempHead.next.val >= insertVal) {
                target.next = tempHead.next;
                tempHead.next = target;
                findPos = true;
                break;
            }
            if (tempHead.val > tempHead.next.val) {
                transNode = tempHead;
            }
            /**
             * 绕了一圈没找到合适插入位置
             */
            if (tempHead.next == head) {
                break;
            }
            tempHead = tempHead.next;
        }

        if (!findPos) {
            if (transNode == null) {
                target.next = tempHead.next;
                tempHead.next = target;
            } else {
                target.next = transNode.next;
                transNode.next = target;
            }
        }

        return head;
    }
}

class Node {
    public int val;
    public Node next;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _next) {
        val = _val;
        next = _next;
    }
}